#pragma once

namespace BTreeDetail
{
	template <size_t Deg>
	concept MinDeg = Deg > 1;
	template <size_t Deg>
	constexpr auto DataMax = std::ratio_subtract<std::ratio<std::ratio_multiply<std::ratio<Deg>, std::ratio<2>>::num>, std::ratio<1>>::num;
	template <size_t Deg>
	constexpr auto SplitDeg = std::ratio_subtract<std::ratio<Deg>, std::ratio<1>>::num;

	template <typename, size_t Deg> requires MinDeg<Deg>
	struct DataNode;
	template <typename, size_t Deg> requires MinDeg<Deg>
	struct InnNode;
}

template <typename Key, size_t Deg = 2>
struct BTree
{
	using POwnerPtr = std::shared_ptr<BTree*>;
	using DataNode = BTreeDetail::DataNode<Key, Deg>;
	using InnNode = BTreeDetail::InnNode<Key, Deg>;
	using DataList = std::list<DataNode*>;
	using DataListIt = DataList::iterator;

	POwnerPtr _ppSelf;
	InnNode* _root = NULL;

	BTree();
	virtual ~BTree();
	auto insert(const Key& k)->std::pair<DataListIt, bool>;
	auto erase(const Key& k)->std::pair<DataListIt, bool>;
	auto erase(const Key& k, InnNode* pMergeNode)->std::pair<DataListIt, bool>;
	template <typename Func>
	auto show(std::ostream& os, Func func) const->std::ostream&;
	bool verify();
};

#include "BTreeImpl.h"